This invention relates to rendering three dimensional objects and/or volumes on a graphics computer. More specifically, the invention relates to ordering polyhedral cells of volumes in a visibility order for efficient visualization.
A visibility ordering of a set of objects, from a given viewpoint, is a total order on the objects such that if object A obstructs object B, then B precedes A in the ordering. Such orderings are extremely useful in computer graphics. Since the late 1960s, several algorithms have been proposed for computing visibility ordering of objects. The classic article by Sutherland, Sproull and Schumacker (xe2x80x9cA Characterization of Ten Hidden-Surface Algorithmsxe2x80x9d, ACM Computing Surveys, 1974), summarizes the early work in the area. At that point, the focus of the visibility ordering work was performing hidden-surface removal. With the advent of the z-buffer, computing visibility orderings was not so important anymore, since such computations were expensive, and the z-buffer provided a simple and effective (hardware) solution to the hidden-surface removal problem.
In the late 1980s, volume rendering, and other graphics techniques were developed, which again required solutions to the visibility ordering problem. In these techniques, it did not suffice to simply flag whether a particular surface (or piece thereof) was visible, but it was necessary to actually compute a global ordering, which then could be used to paint them on the screen in the right order. In Max, Hanranhan, Crawfis (xe2x80x9cArea and Volume Coherence for Efficient Visualization of 3D Scalar Functionsxe2x80x9d, pp 27-33, Computer Graphics (San Diego Workshop on Volume Visualization, 1990)), a technique is proposed which can be used to compute visibility ordering of a special kind of mesh, namely a Delaunay triangulation. In Peter Williams (xe2x80x9cVisibility Ordering Meshed Polyhedraxe2x80x9d, ACM Transactions on Graphics, 1992), a more general technique was proposed, which still only worked correctly for special kind of meshes, in particular, meshes composed of convex cells, which have no holes, and where the boundary of the whole set of cells was convex. In this work, some heuristics for general datasets were proposed.
The first published solution to an efficient technique for computing the xe2x80x9cexactxe2x80x9d (that is, correct) visibility ordering of a set of polyhedral cells was proposed in Stein, Becker, and Max (xe2x80x9cSorting and hardware assisted rendering for volume visualizationxe2x80x9d, Symposium on Volume Visualization, 1994). There, an extension of the previous work of Newell, Newell and Sancha (xe2x80x9cSolution to the hidden surface problemxe2x80x9d, Proc ACM National Conference, 1972) was proposed. Later, in Williams, Max, and Stein (xe2x80x9cA high accuracy volume renderer for unstructured dataxe2x80x9d, IEEE Transactions on Visualization and Computer Graphics, 1998), a faster variation of the technique is described. A technique similar to Stein et al, is also described in Karasick, Lieber, Nackman, and Rajan (xe2x80x9cVisualization of three-dimensional Delaunay meshesxe2x80x9d, Algorithmica 1997).
Prior art can be roughly divided into three classes: (I) exact visibility-ordering techniques which are general (that is, work for all types of meshes); (II) exact visibility-ordering techniques which have limited applicability (that is, only work correctly for certain types of meshes); (III) and heuristic techniques, which only approximate the visibility ordering of polyhedral cells.
Class I algorithms have quadratic complexity, and have shown to be very slow in practice, and not suitable for use in any kind of interactive application.
Class II algorithms, although fast and suitable for use, have limited scope, and can only be applied for certain types of meshes.
Class III algorithms are not suited for use in interactive applications, mainly because they usually lead to errors in the computed images, which in general might lead to undesirable results. Using Class III algorithms compromises not only the quality of the visualization, but ultimately it can lead to incorrect conclusions. For instance, a medical doctor can not rely on results obtained by using such techniques.
An object of this invention is an improved method for computing visibility ordering of polyhedral cells.
An object of this invention is an improved system and method for rendering three dimensional volumes.
An object of this invention is an improved system and method for quickly and efficiently rendering three dimensional volumes represented by large data sets.
An object of this invention is an improved system and method for quickly and efficiently rendering three dimensional volumes represented by unstructured (non convex) and large data sets where the volumes are sorted in a visibility order.
We propose a system and method for efficiently computing the visibility ordering of polyhedral cells.
In order to compute such orderings, our invention builds an ordering graph, composed of oriented edges between two cells. Each edge (A,B) corresponds to the fact that cell A has to be projected, or rendered, before B.
Our invention comprises a set of ordering relations and rules that can be shown to generate, if one exists, a global ordering of the polyhedral cell complex. Our invention uses three different types of edges to accomplish this: Meshed Polyhedra Visibility Ordering (MPVO), Binary Space Partition (BSP) and Partially Projected Cell (PPC) edges, where MPVO edges are prior art described in xe2x80x9cVisibility Ordering Meshed Polyhedraxe2x80x9d by Peter Williams, and BSP and PPC edges are new for our invention.
MPVO edges exist between two cells that share a face.
BSP edges: In order to define the BSP edges, we must first compute a BSP-tree of the boundary faces of the cell complex. During this construction, some of the boundary faces of the cells will be xe2x80x98cutxe2x80x99 by the BSP-tree xe2x80x98extendedxe2x80x99 faces, into multiple pieces. If we say C is the boundary cell, and cxe2x80x2, cxe2x80x3, and so on, are the pieces of its boundary faces, we define BSP_edge (cxe2x80x2, C) to mean that cell C can only be projected after cxe2x80x2 has been projected by the BSP.
PPC edges: We say a cell C is in the PPC if one of the pieces that compose it, say cxe2x80x2, has been projected by the BSP, but there exist other pieces of cell C that have not been projected. In this case, our system needs to perform additional checks to ensure cells are not being projected out of order. This is accomplished by performing xe2x80x98ray shootingxe2x80x99 queries, which we call XMPVO queries.